{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reconstruct a 2-Row Binary Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reconstructMatrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #重构 2 行二进制矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个&nbsp;<code>2</code>&nbsp;行 <code>n</code> 列的二进制数组：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>矩阵是一个二进制矩阵，这意味着矩阵中的每个元素不是&nbsp;<code>0</code>&nbsp;就是&nbsp;<code>1</code>。</li>\n",
    "\t<li>第 <code>0</code> 行的元素之和为&nbsp;<code>upper</code>。</li>\n",
    "\t<li>第 <code>1</code> 行的元素之和为 <code>lower</code>。</li>\n",
    "\t<li>第 <code>i</code> 列（从 <code>0</code> 开始编号）的元素之和为&nbsp;<code>colsum[i]</code>，<code>colsum</code>&nbsp;是一个长度为&nbsp;<code>n</code>&nbsp;的整数数组。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你需要利用&nbsp;<code>upper</code>，<code>lower</code>&nbsp;和&nbsp;<code>colsum</code>&nbsp;来重构这个矩阵，并以二维整数数组的形式返回它。</p>\n",
    "\n",
    "<p>如果有多个不同的答案，那么任意一个都可以通过本题。</p>\n",
    "\n",
    "<p>如果不存在符合要求的答案，就请返回一个空的二维数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>upper = 2, lower = 1, colsum = [1,1,1]\n",
    "<strong>输出：</strong>[[1,1,0],[0,0,1]]\n",
    "<strong>解释：</strong>[[1,0,1],[0,1,0]] 和 [[0,1,1],[1,0,0]] 也是正确答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>upper = 2, lower = 3, colsum = [2,2,1,1]\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]\n",
    "<strong>输出：</strong>[[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= colsum.length &lt;= 10^5</code></li>\n",
    "\t<li><code>0 &lt;= upper, lower &lt;= colsum.length</code></li>\n",
    "\t<li><code>0 &lt;= colsum[i] &lt;= 2</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reconstruct-a-2-row-binary-matrix](https://leetcode.cn/problems/reconstruct-a-2-row-binary-matrix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reconstruct-a-2-row-binary-matrix](https://leetcode.cn/problems/reconstruct-a-2-row-binary-matrix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n1\\n[1,1,1]', '2\\n3\\n[2,2,1,1]', '5\\n5\\n[2,1,2,0,1,0,1,2,0,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        if sum(colsum) == upper + lower:\n",
    "            res = []\n",
    "            l = len(colsum)\n",
    "            for i in range(l):\n",
    "                if colsum[i] == 2:\n",
    "                    colsum[i] -= 1\n",
    "                    res.append(1)\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    res.append(0)\n",
    "            count = 0\n",
    "            while upper > 0 and count < l:\n",
    "                if colsum[count] == 1 and res[count] == 0:\n",
    "                    res[count] = 1\n",
    "                    colsum[count] = 0\n",
    "                    upper -= 1\n",
    "                count += 1\n",
    "            if upper > 0 or max(colsum)>1:\n",
    "                return []\n",
    "            else:\n",
    "                return [res,colsum]\n",
    "\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n_col = len(colsum)\n",
    "        res = []\n",
    "        colsum_cnt = Counter(colsum)\n",
    "        one_cnt = colsum_cnt[1]\n",
    "        two_cnt = colsum_cnt[2]\n",
    "        upper_one = upper-two_cnt\n",
    "        if one_cnt+2*two_cnt!=upper+lower or two_cnt>min(upper,lower):\n",
    "            return []\n",
    "        for i in range(n_col):\n",
    "            if colsum[i] == 2:\n",
    "                res.append(1)\n",
    "                colsum[i] = 1\n",
    "            elif upper_one>0 and colsum[i]==1:\n",
    "                res.append(1)\n",
    "                upper_one-=1\n",
    "                colsum[i] = 0\n",
    "            else:\n",
    "                res.append(0)\n",
    "        return [res,colsum]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        if sum(colsum) == upper + lower:\n",
    "            res = []\n",
    "            l = len(colsum)\n",
    "            for i in range(l):\n",
    "                if colsum[i] == 2:\n",
    "                    colsum[i] -= 1\n",
    "                    res.append(1)\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    res.append(0)\n",
    "            count = 0\n",
    "            while upper > 0 and count < l:\n",
    "                if colsum[count] == 1 and res[count] == 0:\n",
    "                    res[count] = 1\n",
    "                    colsum[count] = 0\n",
    "                    upper -= 1\n",
    "                count += 1\n",
    "            print(res)\n",
    "            print(colsum)\n",
    "            if upper > 0 or max(colsum)>1:\n",
    "                return []\n",
    "            else:\n",
    "                return [res,colsum]\n",
    "\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        sum_val = 0\n",
    "        two_num = 0\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 2:\n",
    "                two_num += 1\n",
    "            sum_val += colsum[i]\n",
    "        if sum_val != upper + lower or min(upper, lower) < two_num:\n",
    "            return []\n",
    "        upper -= two_num\n",
    "        lower -= two_num\n",
    "        res = [[0] * n for _ in range(2)]\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 2:\n",
    "                res[0][i] = res[1][i] = 1\n",
    "            elif colsum[i] == 1:\n",
    "                if upper > 0:\n",
    "                    res[0][i] = 1\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    res[1][i] = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        sumV = sum(colsum)\n",
    "        if sumV != (upper + lower):\n",
    "            return []\n",
    "        count = colsum.count(2)\n",
    "        if count > upper or count > lower:\n",
    "            return []\n",
    "        \n",
    "\n",
    "        length = len(colsum)\n",
    "        matrix = [[0] * length for i in range(2)]\n",
    "        for i in range(length):\n",
    "            if colsum[i] == 2:\n",
    "                matrix[0][i] += 1\n",
    "                colsum[i] -= 1\n",
    "                upper -= 1\n",
    "            if upper == 0:\n",
    "                break\n",
    "            \n",
    "        if upper:\n",
    "            for i in range(length):\n",
    "                if not matrix[0][i] and colsum[i] == 1:\n",
    "                    matrix[0][i] += 1\n",
    "                    colsum[i] -= 1\n",
    "                    upper -= 1\n",
    "                if upper == 0:\n",
    "                    break\n",
    "\n",
    "        matrix[1] = colsum\n",
    "\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        if upper+lower!=sum(colsum):\n",
    "            return []\n",
    "        res = [[], []]\n",
    "        for x in colsum:\n",
    "            a,b = (x//2,x//2) if x!=1 else (1,0) if upper>=lower else (0,1)\n",
    "            upper,lower = upper-a,lower-b\n",
    "            res[0].append(a)\n",
    "            res[1].append(b)\n",
    "        return res if upper==lower==0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        length = len(colsum)  # 矩阵的列数\n",
    "        # 首先创建一个矩阵，初始化全为0\n",
    "        ans = [[0] * length, [0] * length]\n",
    "\n",
    "        # 遍历\n",
    "        for i in range(length):\n",
    "            if colsum[i] == 2:\n",
    "                ans[0][i] = 1\n",
    "                ans[1][i] = 1\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "            elif colsum[i] == 1:\n",
    "                if upper > lower:\n",
    "                    ans[0][i] = 1\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    ans[1][i] = 1\n",
    "                    lower -= 1\n",
    "\n",
    "            \n",
    "        # 判断\n",
    "        if upper != 0 or lower != 0:\n",
    "            return []\n",
    "        else:\n",
    "            return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        res = [[0]* n for i in range(2)]\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 2:\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "                res[0][i] = res[1][i] = 1\n",
    "            elif colsum[i] == 1:\n",
    "                if upper < lower:\n",
    "                    lower -= 1\n",
    "                    res[1][i] = 1\n",
    "                else:\n",
    "                    upper -= 1\n",
    "                    res[0][i] = 1\n",
    "            if upper < 0 or lower < 0:\n",
    "                return []\n",
    "            # print(upper, lower, res)\n",
    "        return res if upper == 0 and lower == 0 else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        arr = [[0] * n for _ in range(2)]\n",
    "        c = Counter(colsum)\n",
    "        if upper + lower != sum(colsum) or c.get(2, 0) > min(upper, lower):\n",
    "            return []\n",
    "\n",
    "        cnt = upper - c.get(2, 0)\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 2:\n",
    "                arr[0][i] = 1\n",
    "                arr[1][i] = 1\n",
    "            elif colsum[i] == 1:\n",
    "                if cnt > 0:\n",
    "                    arr[0][i] = 1\n",
    "                    cnt -= 1\n",
    "                else:\n",
    "                    arr[1][i] = 1\n",
    "        \n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        lieshu = len(colsum)\n",
    "        if sum(colsum)!=upper+lower:\n",
    "            return []\n",
    "        dp = [[0]*lieshu for _ in range(2)]\n",
    "        hang1_count = 0 \n",
    "        for i in range(len(colsum)):\n",
    "            if colsum[i] ==2 and hang1_count<upper:\n",
    "                dp[0][i] = 1\n",
    "                colsum[i] -=1\n",
    "                hang1_count+=1\n",
    "        for i in range(len(colsum)):\n",
    "            if colsum[i] ==1 and hang1_count<upper and dp[0][i]!=1:\n",
    "                dp[0][i] = 1\n",
    "                colsum[i] -=1\n",
    "                hang1_count+=1\n",
    "        hang2_count = 0\n",
    "        for i in range(len(colsum)):\n",
    "            if colsum[i] ==1 and hang2_count<lower and dp[1][i]!=1:\n",
    "                dp[1][i] = 1\n",
    "                colsum[i] -=1\n",
    "                hang2_count+=1\n",
    "        print(dp)\n",
    "        print(hang1_count,hang2_count)\n",
    "\n",
    "        return dp if hang2_count==lower and hang1_count==upper else []\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        # if sum(colsum) != upper + lower:\n",
    "        #     return []\n",
    "        # if any(c > 2 for c in colsum):\n",
    "        #     return []\n",
    "        twos = [i for i in range(len(colsum)) if colsum[i] == 2]\n",
    "        if len(twos) > min(upper,lower):\n",
    "            return []\n",
    "        \n",
    "        up = [0]*len(colsum)\n",
    "        low = [0]*len(colsum)\n",
    "        for i in twos:\n",
    "            low[i] = up[i] = 1\n",
    "        upper -= len(twos)\n",
    "        lower -= len(twos)\n",
    "\n",
    "        for i in range(len(colsum)):\n",
    "            if colsum[i] == 1:\n",
    "                if upper > 0:\n",
    "                    upper -= 1\n",
    "                    up[i] = 1\n",
    "                else:\n",
    "                    lower -= 1\n",
    "                    low[i] = 1\n",
    "\n",
    "        return [up,low] if lower == upper == 0 else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        if sum(colsum) != upper+lower:return []\n",
    "        n = len(colsum)\n",
    "        upp,low = [0]*n,[0]*n\n",
    "        for i in range(n):\n",
    "            if colsum[i] > 2:\n",
    "                return []\n",
    "            if colsum[i] == 2:\n",
    "                upp[i], low[i] = 1,1\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "            if colsum[i] == 1:\n",
    "                if upper > lower:\n",
    "                    upper -= 1\n",
    "                    upp[i] = 1\n",
    "                else:\n",
    "                    lower -= 1\n",
    "                    low[i] = 1\n",
    "            if upper < 0 or lower < 0:\n",
    "                return []\n",
    "        \n",
    "        return [upp,low]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        sum_val = 0\n",
    "        two_num = 0\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 2:\n",
    "                two_num += 1\n",
    "            sum_val += colsum[i]\n",
    "        if sum_val != upper + lower or min(upper, lower) < two_num:\n",
    "            return []\n",
    "        upper -= two_num\n",
    "        lower -= two_num\n",
    "        res = [[0] * n for _ in range(2)]\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 2:\n",
    "                res[0][i] = res[1][i] = 1\n",
    "            elif colsum[i] == 1:\n",
    "                if upper > 0:\n",
    "                    res[0][i] = 1\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    res[1][i] = 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        if upper+lower != sum(colsum):\n",
    "            return []\n",
    "        n = len(colsum)\n",
    "        '''\n",
    "        ans = [[0]*n]*2 这种方式属于浅拷贝，两行都指向同一个地址，赋值时会同时改变两行的值\n",
    "        '''\n",
    "        ans = [[0]*n for _ in range(2)]\n",
    "        for i,num in enumerate(colsum):\n",
    "            if num == 2:\n",
    "                ans[0][i],ans[1][i] = 1,1\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "        for i,num in enumerate(colsum):\n",
    "            if num == 1:\n",
    "                if upper > 0:\n",
    "                    ans[0][i] = 1\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    ans[1][i] = 1\n",
    "        if upper > 0:\n",
    "            return []\n",
    "        else:\n",
    "            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        n = len(colsum)\n",
    "        sum_all = sum(colsum)\n",
    "\n",
    "        if (upper < 0 or lower < 0) or (upper > n or lower > n) or sum_all != upper + lower:\n",
    "            return res\n",
    "\n",
    "        ans = [[0] * n for i in range(2)]\n",
    "\n",
    "        for j, v in enumerate(colsum):\n",
    "            if v == 2:\n",
    "                ans[0][j] = ans[1][j] = 1\n",
    "                upper, lower = upper - 1, lower - 1\n",
    "\n",
    "            if v == 1:\n",
    "                if upper > lower:\n",
    "                    upper -= 1\n",
    "                    ans[0][j] = 1\n",
    "                else:\n",
    "                    lower -= 1\n",
    "                    ans[1][j] = 1\n",
    "\n",
    "            if lower == 0 and upper == 0:\n",
    "                res = ans\n",
    "                break\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        sumOfcol = 0 # 记录colsum数组的总和\n",
    "        twoOfcol = 0 # 记录colsum数组中数字2出现的次数\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 2:\n",
    "                twoOfcol += 1 \n",
    "            sumOfcol += colsum[i]\n",
    "        if sumOfcol != upper + lower or twoOfcol > min(upper, lower):  # 如果2出现次数大于min(upper,lower)也不存在这样的矩阵，\n",
    "            return []\n",
    "        \n",
    "\n",
    "        res = [[0]*n for _ in range(2)]\n",
    "        upper -= twoOfcol   # upper中colsum数组中数字1的个数（除去upper和lower同时为1的情况）\n",
    "        lower -= twoOfcol   # lower中colsum数组中数字1的个数\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 2:\n",
    "                res[0][i] = res[1][i] = 1\n",
    "            elif colsum[i] == 1:\n",
    "                if upper > 0: \n",
    "                    res[0][i] = 1  # 第一行为1 \n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    res[1][i] = 1  # 第二行为1\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        if sum(colsum)!=upper+lower:return []\n",
    "        n=len(colsum)\n",
    "        num=[[0]*n for _ in range(2)]\n",
    "        for i in range(n):\n",
    "            if colsum[i]==2:\n",
    "                if upper and lower:\n",
    "                    num[0][i]=1\n",
    "                    num[1][i]=1\n",
    "                    upper-=1\n",
    "                    lower-=1\n",
    "                else: return []\n",
    "        for i in range(n):\n",
    "            if colsum[i]==1:\n",
    "                if upper:\n",
    "                    num[0][i]=1\n",
    "                    upper-=1\n",
    "                elif lower:\n",
    "                    num[1][i]=1\n",
    "                    lower-=1\n",
    "                else: return []\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        numsum = sum(colsum)\n",
    "        n = len(colsum)\n",
    "        twocount = colsum.count(2)\n",
    "        if numsum - upper - lower != 0 or upper < twocount or lower < twocount:\n",
    "            return []\n",
    "        up = upper - twocount\n",
    "        res1= [0] * n\n",
    "        res2 = [0] * n\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 2:\n",
    "                res1[i] = 1\n",
    "                res2[i] = 1\n",
    "            elif colsum[i] == 1:\n",
    "                if up > 0:\n",
    "                    res1[i] = 1\n",
    "                    up -= 1\n",
    "                else:\n",
    "                    res2[i] = 1\n",
    "        return [res1,res2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        if sum(colsum) != upper+lower or colsum.count(2)>min(upper,lower):\n",
    "            return []\n",
    "        else:\n",
    "            rest = upper-lower\n",
    "            ans = [[0]*len(colsum) for _ in range(2)]\n",
    "            for i,col in enumerate(colsum):\n",
    "                if col == 2:\n",
    "                    ans[0][i]=ans[1][i]=1\n",
    "                elif col == 1:\n",
    "                    if rest > 0:\n",
    "                        ans[0][i] = 1\n",
    "                        rest -= 1\n",
    "                    else:\n",
    "                        ans[1][i] = 1\n",
    "                        rest += 1\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        if sum(colsum)!=upper+lower:return []\n",
    "        n=len(colsum)\n",
    "        num=[[0]*n for _ in range(2)]\n",
    "        for i in range(n):\n",
    "            if colsum[i]==2:\n",
    "                if upper and lower:\n",
    "                    num[0][i]=1\n",
    "                    num[1][i]=1\n",
    "                    upper-=1\n",
    "                    lower-=1\n",
    "                else: return []\n",
    "        for i in range(n):\n",
    "            if colsum[i]==1:\n",
    "                if upper:\n",
    "                    num[0][i]=1\n",
    "                    upper-=1\n",
    "                elif lower:\n",
    "                    num[1][i]=1\n",
    "                    lower-=1\n",
    "                else: return []\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        if upper + lower != sum(colsum):\n",
    "            return []\n",
    "        ans = [[0 for _ in range(len(colsum))] for _ in range(2)]\n",
    "        for i in range(len(colsum)):\n",
    "            if colsum[i] == 2:\n",
    "                ans[0][i] = 1\n",
    "                ans[1][i] = 1\n",
    "        s1 = upper - sum(ans[0])\n",
    "        s2 = lower - sum(ans[1])\n",
    "        if s1 < 0 or s2 < 0:\n",
    "            return []\n",
    "        for i in range(len(colsum)):\n",
    "            if colsum[i] == 1:\n",
    "                if s1 > 0:\n",
    "                    ans[0][i] = 1\n",
    "                    s1 -= 1\n",
    "                elif s2 > 0:\n",
    "                    ans[1][i] = 1\n",
    "                    s2 -= 1\n",
    "                else:\n",
    "                    return []\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        if sum(colsum) != upper + lower:\n",
    "            return []\n",
    "\n",
    "        array = [[0] * n for _ in range(2)]\n",
    "        for j in range(n):\n",
    "            if colsum[j] == 2:\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "                array[0][j] = array[1][j] = 1\n",
    "            elif colsum[j] == 1:\n",
    "                if upper >= lower:\n",
    "                    array[0][j] = 1\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    array[1][j] = 1\n",
    "                    lower -= 1\n",
    "\n",
    "            if upper < 0 or lower < 0:\n",
    "                return []\n",
    "        return array\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        if upper + lower != sum(colsum):\n",
    "            return []\n",
    "        res = [[0] * len(colsum) for _ in range(2)]\n",
    "        cnt_both = sum(col == 2 for col in colsum)\n",
    "        upper -= cnt_both\n",
    "        if upper < 0 or lower - cnt_both < 0:\n",
    "            return []\n",
    "        for i in range(len(colsum)):\n",
    "            col = colsum[i]\n",
    "            if col == 2:\n",
    "                res[0][i] = 1\n",
    "                res[1][i] = 1\n",
    "            elif col == 1:\n",
    "                if upper:\n",
    "                    res[0][i] = 1\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    res[1][i] = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        two_sum = 0\n",
    "        sum=0\n",
    "        for i in range(len(colsum)):\n",
    "            if colsum[i]==2:\n",
    "                two_sum+=1\n",
    "            sum+=colsum[i]\n",
    "        if sum != upper+lower or two_sum>min(upper,lower):\n",
    "            return []\n",
    "        res=[[0 for i in range(len(colsum))] for _ in range(2)]\n",
    "        upper -= two_sum\n",
    "        lower -= two_sum\n",
    "        for i in range(len(colsum)):\n",
    "            if colsum[i]==2:\n",
    "                res[0][i] = res[1][i] = 1\n",
    "            elif colsum[i]==1:\n",
    "                if upper>0:\n",
    "                    res[0][i] = 1\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    res[1][i]=1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        cnt = Counter(colsum)\n",
    "        a, b, c, d = 0, 0, 0, 0    # 0,0   0,1   1,0    1,1\n",
    "        a, d = cnt[0], cnt[2]\n",
    "        c = upper - d\n",
    "        b = lower - d\n",
    "        print(cnt, a, b, c, d)\n",
    "        if c < 0 or b < 0 or b+c != cnt[1]:\n",
    "            return []\n",
    "        res = [[], []]\n",
    "        for x in colsum:\n",
    "            if x == 2:\n",
    "                res[0].append(1)\n",
    "                res[1].append(1)\n",
    "            elif x == 0:\n",
    "                res[0].append(0)\n",
    "                res[1].append(0)\n",
    "            else:\n",
    "                if b > 0:\n",
    "                    res[0].append(0)\n",
    "                    res[1].append(1)\n",
    "                    b -= 1\n",
    "                else:\n",
    "                    res[0].append(1)\n",
    "                    res[1].append(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        if sum(colsum) != upper + lower:\n",
    "            return []\n",
    "        two = sum([1 for x in colsum if x == 2])\n",
    "        one = sum([1 for x in colsum if x == 1])\n",
    "        zero = sum([1 for x in colsum if x == 0])\n",
    "        upper = upper - two\n",
    "        lower = lower - two\n",
    "        upperset = []\n",
    "        lowerset = []\n",
    "        for i in colsum:\n",
    "            if i == 2:\n",
    "                upperset.append(1)\n",
    "                lowerset.append(1)\n",
    "            if i == 0:\n",
    "                upperset.append(0)\n",
    "                lowerset.append(0)\n",
    "            if i == 1:\n",
    "                if upper > 0:\n",
    "                    upperset.append(1)\n",
    "                    lowerset.append(0)\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    upperset.append(0)\n",
    "                    lowerset.append(1)\n",
    "                    lower -= 1\n",
    "        if upper!=0 or lower != 0:\n",
    "            return []\n",
    "        return [upperset, lowerset]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        if sum(colsum) != upper + lower: return []\n",
    "\n",
    "        count_min = len([0 for _ in colsum if _ == 2])\n",
    "        if count_min > upper or count_min > lower: return []\n",
    "        upper -= count_min\n",
    "        lower -= count_min\n",
    "        \n",
    "        ret_list = [[], []]\n",
    "        for i in colsum:\n",
    "            if i == 2:\n",
    "                ret_list[0].append(1)\n",
    "                ret_list[1].append(1)\n",
    "            elif i == 0:\n",
    "                ret_list[0].append(0)\n",
    "                ret_list[1].append(0)\n",
    "            else:\n",
    "                if upper:\n",
    "                    ret_list[0].append(1)\n",
    "                    ret_list[1].append(0)\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    ret_list[0].append(0)\n",
    "                    ret_list[1].append(1)\n",
    "                    lower -= 1\n",
    "        \n",
    "        return ret_list\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        result = [[], []]\n",
    "        if upper + lower != sum(colsum):\n",
    "            return []\n",
    "        for item in colsum:\n",
    "            if item == 2:\n",
    "                result[0].append(1)\n",
    "                upper -= 1\n",
    "                result[1].append(1)\n",
    "                lower -= 1\n",
    "            elif item == 0:\n",
    "                result[0].append(0)\n",
    "                result[1].append(0)\n",
    "            else:\n",
    "                if upper > lower:\n",
    "                    result[0].append(1)\n",
    "                    upper -= 1\n",
    "                    result[1].append(0)\n",
    "                else:\n",
    "                    result[0].append(0)\n",
    "                    result[1].append(1)\n",
    "                    lower -= 1\n",
    "        if upper or lower:\n",
    "            return []\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        if n == 0:\n",
    "            return []\n",
    "        ans = [[0] * n for _ in range(2)]\n",
    "        for x , y in enumerate(colsum):\n",
    "            if y == 0:\n",
    "                ans[0][x] = ans[1][x] = 0\n",
    "            \n",
    "            if y == 2:\n",
    "                ans[0][x] = ans[1][x] = 1\n",
    "                upper = upper - 1\n",
    "                lower = lower - 1\n",
    "\n",
    "            if y == 1:\n",
    "                if upper > lower:\n",
    "                    ans[0][x] = 1\n",
    "                    ans[1][x] = 0\n",
    "                    upper = upper - 1\n",
    "                else:\n",
    "                    ans[0][x] = 0\n",
    "                    ans[1][x] = 1\n",
    "                    lower = lower - 1\n",
    "        if upper == 0 and lower == 0:\n",
    "            return ans\n",
    "        else:\n",
    "            return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        if upper + lower != sum(colsum):\n",
    "            return []\n",
    "        l = len(colsum)\n",
    "        result = [[],[]]\n",
    "        for i in range(l):\n",
    "            if colsum[i] == 2:\n",
    "                result[0].append(1) \n",
    "                result[1].append(1)\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "                if(upper<0 or lower <0):\n",
    "                    return []\n",
    "            elif colsum[i] == 0:\n",
    "                result[0].append(0)\n",
    "                result[1].append(0)\n",
    "            else:\n",
    "                result[0].append(-1)\n",
    "                result[1].append(-1)\n",
    "        for i in range(l):\n",
    "            if colsum[i] == 1:\n",
    "                if upper > 0:\n",
    "                    upper -= 1\n",
    "                    result[0][i] = 1\n",
    "                    result[1][i] = 0\n",
    "                elif lower > 0:\n",
    "                    lower -= 1\n",
    "                    result[0][i] = 0\n",
    "                    result[1][i] = 1\n",
    "                else:\n",
    "                    return []\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        ans = [[0] * n for _ in range(2)]\n",
    "        for i, col in enumerate(colsum):\n",
    "            if col == 2:\n",
    "                ans[0][i] = ans[1][i] = 1\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "            if col == 1:\n",
    "                if upper > lower:\n",
    "                    ans[0][i] = 1\n",
    "                    upper -= 1\n",
    "                else: \n",
    "                    ans[1][i] = 1\n",
    "                    lower -= 1\n",
    "        if upper < 0 or lower < 0:\n",
    "            return []\n",
    "        return ans if lower == upper == 0 else []\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        arr = [[0] * n for _ in range(2)]\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 2:\n",
    "                arr[0][i], arr[1][i] = 1, 1\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "                colsum[i] = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 1:\n",
    "                if upper > 0:\n",
    "                    arr[0][i] = 1\n",
    "                    colsum[i] = 0\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    arr[1][i] = 1\n",
    "                    lower -= 1\n",
    "        \n",
    "        if 0 == upper == lower:\n",
    "            return arr\n",
    "        else:\n",
    "            return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        ans = [[0] * n for _ in range(2)]\n",
    "\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 2:\n",
    "                ans[0][i] = 1\n",
    "                ans[1][i] = 1\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "            if colsum[i] == 1:\n",
    "                if upper > lower:\n",
    "                    ans[0][i] = 1\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    ans[1][i] = 1\n",
    "                    lower -= 1\n",
    "        return ans if lower == upper == 0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "\n",
    "        n = len(colsum)\n",
    "        matrix = [[0] * n for _ in range(2)]\n",
    "\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 2:\n",
    "                if upper == 0 or lower == 0:\n",
    "                    return []\n",
    "                matrix[0][i] = 1\n",
    "                matrix[1][i] = 1\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "            elif colsum[i] == 1:\n",
    "                if upper == 0 and lower == 0:\n",
    "                    return []\n",
    "                if upper > lower:\n",
    "                    matrix[0][i] = 1\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    matrix[1][i] = 1\n",
    "                    lower -= 1\n",
    "\n",
    "        return matrix if upper == 0 and lower == 0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        ans = [[0] * n for _ in range(2)]\n",
    "\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 2:\n",
    "                ans[0][i] = 1\n",
    "                ans[1][i] = 1\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 1:\n",
    "                if upper > 0:\n",
    "                    ans[0][i] = 1\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    ans[1][i] = 1\n",
    "                    lower -= 1\n",
    "    \n",
    "        return ans if lower == upper == 0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        res = [[0]*n for _ in range(2)]\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 2:\n",
    "                res[0][i] = 1\n",
    "                res[1][i] = 1\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            if colsum[i] == 1:\n",
    "                if upper>0:\n",
    "                    res[0][i] = 1\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    res[1][i] = 1\n",
    "                    lower -= 1\n",
    "        if upper == 0 and lower == 0:\n",
    "            return res\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        ans = [[0] * n for _ in range(2)]\n",
    "        for j, v in enumerate(colsum):\n",
    "            if v == 2:\n",
    "                ans[0][j] = ans[1][j] = 1\n",
    "                upper, lower = upper - 1, lower - 1\n",
    "            if v == 1:\n",
    "                if upper > lower:\n",
    "                    upper -= 1\n",
    "                    ans[0][j] = 1\n",
    "                else:\n",
    "                    lower -= 1\n",
    "                    ans[1][j] = 1\n",
    "            if upper < 0 or lower < 0:\n",
    "                return []\n",
    "        return ans if lower == upper == 0 else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        ans = [[0] * n for _ in range(2)]\n",
    "        for j, v in enumerate(colsum):\n",
    "            if v == 2:\n",
    "                ans[0][j] = ans[1][j] = 1\n",
    "                upper, lower = upper - 1, lower - 1\n",
    "            if v == 1:\n",
    "                if upper > lower:\n",
    "                    upper -= 1\n",
    "                    ans[0][j] = 1\n",
    "                else:\n",
    "                    lower -= 1\n",
    "                    ans[1][j] = 1\n",
    "            if upper < 0 or lower < 0:\n",
    "                return []\n",
    "        return ans if lower == upper == 0 else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        ans = [[0 for j in range(n)] for i in range(2)]\n",
    "        if sum(colsum) != lower+upper:\n",
    "            return []\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 0:\n",
    "                continue\n",
    "            elif colsum[i] == 2:\n",
    "                if lower <= 0 or upper <= 0:\n",
    "                    return []\n",
    "                ans[0][i] = 1\n",
    "                ans[1][i] = 1\n",
    "                lower -= 1\n",
    "                upper -= 1\n",
    "            else:\n",
    "                if lower < upper:\n",
    "                    ans[0][i] = 1\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    ans[1][i] = 1\n",
    "                    lower -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        l = len(colsum)\n",
    "        ans = [[0 for i in range(l)],[0 for i in range(l)]]\n",
    "        for i in range(l):\n",
    "            if colsum[i]==2:\n",
    "                ans[0][i]=1\n",
    "                ans[1][i]=1\n",
    "                upper-=1\n",
    "                lower-=1\n",
    "                colsum[i]=0\n",
    "        if upper<0 or lower<0:\n",
    "            return []\n",
    "        for i in range(l):\n",
    "            if colsum[i]==1 and upper>0:\n",
    "                ans[0][i] = 1\n",
    "                upper-=1\n",
    "            elif colsum[i]==1:\n",
    "                ans[1][i] = 1\n",
    "                lower-=1\n",
    "        if lower!=0 or upper!=0:\n",
    "            return []\n",
    "        else:\n",
    "            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        \n",
    "        result = [[0 for _ in range(len(colsum))] for _ in range(2)]\n",
    "        upper -= colsum.count(2)\n",
    "        lower -= colsum.count(2)\n",
    "        # print(upper, lower)\n",
    "        if (lower<0) or( upper<0) or (upper+lower != colsum.count(1)):\n",
    "            return []\n",
    "        for i in range(len(colsum)):\n",
    "            cur_colsum = colsum[i]\n",
    "            if (cur_colsum==2):\n",
    "                result[0][i]=1\n",
    "                result[1][i]=1\n",
    "\n",
    "            elif (cur_colsum==1):\n",
    "                if upper:\n",
    "                    result[0][i] = 1\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    result[1][i] = 1\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        arr = [[0] * n for _ in range(2)]\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 2:\n",
    "                arr[0][i], arr[1][i] = 1, 1\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "                colsum[i] = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 1 and upper > 0:\n",
    "                arr[0][i] = 1\n",
    "                colsum[i] = 0\n",
    "                upper -= 1\n",
    "\n",
    "        for i in range(n):\n",
    "            print(colsum[i])\n",
    "            if colsum[i] == 1:\n",
    "                arr[1][i] = 1\n",
    "                lower -= 1\n",
    "        \n",
    "        if 0 == upper == lower:\n",
    "            return arr\n",
    "        else:\n",
    "            return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        k = 0\n",
    "        k3 = 0\n",
    "        for i in colsum :\n",
    "            k += i\n",
    "            if i == 2:\n",
    "                k3 +=1\n",
    "        if k != lower + upper or k3 > upper or k3 > lower :\n",
    "            return []\n",
    "        l = [[],[]]\n",
    "        k -= k3*2\n",
    "        k1 = upper - k3\n",
    "        k2 = lower - k3\n",
    "        for i in colsum :\n",
    "            if i == 2 :\n",
    "                l[0].append(1)\n",
    "                l[1].append(1)\n",
    "            elif i == 1 :\n",
    "                if k1>0 :\n",
    "                    l[0].append(1)\n",
    "                    l[1].append(0)\n",
    "                    k1 -= 1\n",
    "                else :\n",
    "                    l[0].append(0)\n",
    "                    l[1].append(1)\n",
    "            else :\n",
    "                l[0].append(0)\n",
    "                l[1].append(0)\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        ori_matrix = [[0 for i in range(n)] for j in range(2)]\n",
    "        sum_a = 0\n",
    "        upper_a = upper\n",
    "        lower_a = lower\n",
    "        for ind, each in enumerate(colsum):\n",
    "            sum_a += each\n",
    "            if each == 2:\n",
    "                ori_matrix[0][ind] = 1\n",
    "                ori_matrix[1][ind] = 1\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "                each = 0\n",
    "        if sum_a != upper_a + lower_a:\n",
    "            return []\n",
    "        for ind, each in enumerate(colsum):\n",
    "            if upper < 0 or lower < 0:\n",
    "                return []\n",
    "            if each == 1 and upper != 0:\n",
    "                ori_matrix[0][ind] = 1\n",
    "                upper -= 1\n",
    "                each = 0\n",
    "            elif each == 1 and lower != 0:\n",
    "                ori_matrix[1][ind] = 1\n",
    "                lower -= 1\n",
    "                each = 0\n",
    "            \n",
    "        if upper > 0 or lower > 0:\n",
    "            return []\n",
    "        else:\n",
    "            return ori_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        ans = [[0] * n for _ in range(2)]\n",
    "        for j, v in enumerate(colsum):\n",
    "            if v == 2:\n",
    "                ans[0][j] = ans[1][j] = 1\n",
    "                upper, lower = upper - 1, lower - 1\n",
    "            if v == 1:\n",
    "                if upper > lower:\n",
    "                    upper -= 1\n",
    "                    ans[0][j] = 1\n",
    "                else:\n",
    "                    lower -= 1\n",
    "                    ans[1][j] = 1\n",
    "            if upper < 0 or lower < 0:\n",
    "                return []\n",
    "        return ans if lower == upper == 0 else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        '''\n",
    "        这是一道数学题 算清楚关系就解出来了\n",
    "        难点在于算清楚满足什么条件的情况下该问题有解\n",
    "        lower + upper - 2 * sum_of_two != cnt or lower < sum_of_two or upper < sum_of_two\n",
    "        '''\n",
    "        cnt = 0\n",
    "        sum_of_two = 0\n",
    "        for col in colsum:\n",
    "            cnt += (col == 1)\n",
    "            if col == 2:\n",
    "                sum_of_two += 1\n",
    "        if lower + upper - 2 * sum_of_two != cnt or lower < sum_of_two or upper < sum_of_two:\n",
    "            return []\n",
    "        uppers, lowers = [], []\n",
    "        i = 0\n",
    "        for col in colsum:\n",
    "            if col == 0:\n",
    "                uppers.append(0)\n",
    "                lowers.append(0)\n",
    "            elif col == 2:\n",
    "                uppers.append(1)\n",
    "                lowers.append(1)\n",
    "            else:\n",
    "                if i < upper - sum_of_two:\n",
    "                    uppers.append(1)\n",
    "                    lowers.append(0)\n",
    "                    i += 1\n",
    "                else:\n",
    "                    uppers.append(0)\n",
    "                    lowers.append(1)\n",
    "        return [uppers, lowers]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "\n",
    "        n = len(colsum)\n",
    "\n",
    "        import collections\n",
    "        count = collections.Counter(colsum)\n",
    "\n",
    "        \n",
    "        u1 = upper - count[2]\n",
    "        l1 = lower - count[2]\n",
    "        if u1<0 or l1<0:\n",
    "            return []\n",
    "\n",
    "        res = [[], []]\n",
    "        # 只要为1的数量等于colsum中非0的个数，那就必然存在答案。   \n",
    "        nums1 = count[2] + u1 + l1\n",
    "\n",
    "\n",
    "        if nums1 == n-count[0]: \n",
    "            res = [[0]*n for _ in range(2)]\n",
    "            \n",
    "            # 先把2的位置填满，剩下的随意分配\n",
    "            for i in [idx2 for idx2 in range(n) if colsum[idx2]==2]:\n",
    "                print(i)\n",
    "                res[0][i] = 1\n",
    "                res[1][i] = 1\n",
    "            for i in range(n):\n",
    "                if colsum[i] == 1:\n",
    "                    if u1 > 0:\n",
    "                        res[0][i] = 1\n",
    "                        u1 -= 1\n",
    "                    elif l1 > 0:\n",
    "                        res[1][i] = 1\n",
    "                        l1 -= 1\n",
    "            \n",
    "            return res\n",
    "\n",
    "        else:\n",
    "            return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "\n",
    "        n = len(colsum)\n",
    "\n",
    "        import collections\n",
    "        count = collections.Counter(colsum)\n",
    "\n",
    "        \n",
    "        u1 = upper - count[2]\n",
    "        l1 = lower - count[2]\n",
    "        if u1<0 or l1<0:\n",
    "            return []\n",
    "\n",
    "        res = [[], []]\n",
    "        # 只要为1的数量等于colsum中非0的个数，那就必然存在答案。   \n",
    "        nums1 = count[2] + u1 + l1\n",
    "\n",
    "\n",
    "        if nums1 == n-count[0]: \n",
    "            res = [[0]*n for _ in range(2)]\n",
    "            \n",
    "            # 先把2的位置填满，剩下的随意分配\n",
    "            for i in [idx2 for idx2 in range(n) if colsum[idx2]==2]:\n",
    "                print(i)\n",
    "                res[0][i] = 1\n",
    "                res[1][i] = 1\n",
    "            for i in range(n):\n",
    "                if colsum[i] == 1:\n",
    "                    if u1 > 0:\n",
    "                        res[0][i] = 1\n",
    "                        u1 -= 1\n",
    "                    elif l1 > 0:\n",
    "                        res[1][i] = 1\n",
    "                        l1 -= 1\n",
    "            \n",
    "            return res\n",
    "\n",
    "        else:\n",
    "            return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        if (sum(colsum)!= upper + lower) or max(colsum)>2 or min(colsum)<0 or max(upper,lower)>n:\n",
    "            return []\n",
    "        u = []\n",
    "        l = []\n",
    "        us = 0\n",
    "        special =[]\n",
    "        for i in colsum:\n",
    "            if i==0:\n",
    "                u.append(0)\n",
    "                l.append(0)\n",
    "            elif i==2:\n",
    "                u.append(1)\n",
    "                us+=1\n",
    "                l.append(1)\n",
    "            elif i==1:\n",
    "                if us<upper:\n",
    "                    u.append(1)\n",
    "                    us+=1\n",
    "                    l.append(0)\n",
    "                    special.append(len(u)-1)\n",
    "                else:\n",
    "                    u.append(0)\n",
    "                    l.append(1)\n",
    "        for i in range(sum(u)-upper):\n",
    "            u[special[i]]=0\n",
    "            l[special[i]]=1\n",
    "        if sum(u)!=upper:\n",
    "            return []\n",
    "        return [u,l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        line_1 = [0 for i in colsum]\n",
    "        line_2 = [0 for i in colsum]\n",
    "        for i in range(len(colsum)):\n",
    "            if colsum[i] == 2:\n",
    "                line_1[i] = 1\n",
    "                line_2[i] = 1\n",
    "        n_line_1 = upper - sum(line_1)\n",
    "        n_line_2 = lower - sum(line_2)\n",
    "        total = len(colsum) - sum([1 for i in range(len(colsum)) if colsum[i]==0]) - sum([1 for i in range(len(colsum)) if colsum[i]==2 ])\n",
    "        if total != n_line_1 + n_line_2 or n_line_1 < 0 or n_line_2 < 0:\n",
    "            return []\n",
    "        else:\n",
    "            for i in range(len(colsum)):\n",
    "                if colsum[i] == 1 and n_line_1:\n",
    "                    n_line_1 -= 1\n",
    "                    line_1[i] = 1\n",
    "                elif colsum[i] == 1 and n_line_1==0:\n",
    "                    line_2[i] = 1\n",
    "        return [line_1, line_2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        if upper + lower != sum(colsum):\n",
    "            return []\n",
    "        n = len(colsum)\n",
    "        a = [[0] * n, [0] * n]\n",
    "        s = []\n",
    "        for i, c in enumerate(colsum):\n",
    "            if c == 0:\n",
    "                continue\n",
    "            if c == 1:\n",
    "                s.append(i)\n",
    "                continue\n",
    "            a[0][i] = 1\n",
    "            a[1][i] = 1\n",
    "            upper -= 1\n",
    "            lower -= 1\n",
    "        if upper < 0 or lower < 0:\n",
    "            return []\n",
    "        for i in range(upper):\n",
    "            a[0][s.pop()] = 1\n",
    "        for i in range(lower):\n",
    "            a[1][s.pop()] = 1\n",
    "        return a\n",
    "        \n",
    "        \n",
    "\n",
    "            \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        \n",
    "        n = len(colsum)\n",
    "        cnt1 =0\n",
    "        cnt2 =0\n",
    "        ans =[]\n",
    "        res = [[0]*n for _ in range(2)]\n",
    "        if sum(colsum) != upper+lower:\n",
    "            return []\n",
    "\n",
    "        for i in range(n):\n",
    "            if colsum[i]==2:\n",
    "                res[0][i]+=1\n",
    "                res[1][i]+=1\n",
    "                \n",
    "                upper-=1\n",
    "                lower-=1\n",
    "            elif colsum[i]==1:\n",
    "                ans.append(i)\n",
    "                cnt1+=1 \n",
    "        if upper<0 or lower<0: return []\n",
    "\n",
    "        for i in ans:\n",
    "            if upper>0:\n",
    "                res[0][i]+=1\n",
    "                upper-=1\n",
    "            else:\n",
    "                res[1][i]+=1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        s = 0\n",
    "        s2 = []\n",
    "        for i in range(len(colsum)):\n",
    "            s += colsum[i]\n",
    "            if colsum[i] == 2:\n",
    "                s2.append(i)\n",
    "        print(s, upper + lower)\n",
    "        if s != upper + lower:\n",
    "            return []\n",
    "        if len(s2) > min(upper, lower):\n",
    "            return []\n",
    "        res = [[0] * len(colsum) for _ in range(2)]\n",
    "        # print(res)\n",
    "        count0 = len(s2)\n",
    "        for j in range(len(s2)):\n",
    "            res[0][s2[j]] = 1 \n",
    "            res[1][s2[j]] = 1 \n",
    "        for i in range(len(colsum)):\n",
    "            if colsum[i] == 1:\n",
    "                if count0 < upper:\n",
    "                    res[0][i] = 1\n",
    "                    count0 += 1\n",
    "                else:\n",
    "                    res[1][i] = 1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        lens = len(colsum)\n",
    "        res = [[0]*lens,[0]*lens]\n",
    "        for i in range(lens):\n",
    "            if colsum[i] != 1:\n",
    "                temp = colsum[i] // 2\n",
    "                res[0][i] = temp\n",
    "                res[1][i] = temp\n",
    "                upper -= temp\n",
    "                lower -= temp\n",
    "                if(lower<0) or (upper<0):return []\n",
    "        for j in range(lens):\n",
    "            if colsum[j] == 1:\n",
    "                if upper > 0:\n",
    "                    res[0][j] = 1\n",
    "                    upper -= 1\n",
    "                elif lower > 0:\n",
    "                    res[1][j] = 1\n",
    "                    lower -= 1\n",
    "                else:\n",
    "                    res = []\n",
    "        if not (upper==0 and lower==0):\n",
    "            res = []\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        if upper + lower != sum(colsum):\n",
    "            return []\n",
    "        one_index = []\n",
    "        result = [[], []]\n",
    "        for i in range(len(colsum)):\n",
    "            if colsum[i] == 0:\n",
    "                result[0].append(0)\n",
    "                result[1].append(0)\n",
    "            elif colsum[i] == 2:\n",
    "                result[0].append(1)\n",
    "                result[1].append(1)\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "            else:\n",
    "                one_index.append(i)\n",
    "                result[0].append(0)\n",
    "                result[1].append(0)\n",
    "        if upper < 0 or lower < 0:\n",
    "            return []\n",
    "            \n",
    "        for i in one_index:\n",
    "            if upper:\n",
    "                result[0][i] = 1\n",
    "                result[1][i] = 0\n",
    "                upper -= 1\n",
    "            else:\n",
    "                result[0][i] = 0\n",
    "                result[1][i] = 1\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n=len(colsum)\n",
    "        res=[[],[]]\n",
    "        for i in range(n):\n",
    "            if colsum[i]==0:\n",
    "                res[0].append(0)\n",
    "                res[1].append(0)               \n",
    "            elif colsum[i]==1:\n",
    "                if upper>0 or lower>0:\n",
    "                    if upper>lower:\n",
    "                        upper-=1\n",
    "                        res[0].append(1)\n",
    "                        res[1].append(0)\n",
    "                    else:\n",
    "                        lower-=1\n",
    "                        res[0].append(0)\n",
    "                        res[1].append(1)\n",
    "                else:\n",
    "                    return []\n",
    "            else:\n",
    "                if upper>0 and lower>0:\n",
    "                    upper-=1\n",
    "                    lower-=1\n",
    "                    res[0].append(1)\n",
    "                    res[1].append(1)\n",
    "                else:\n",
    "                    return []\n",
    "        \n",
    "        return res if upper==lower==0 else []\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        left,right=[],[]\n",
    "        for num in colsum:\n",
    "            if num==0:\n",
    "                left.append(0)\n",
    "                right.append(0)\n",
    "            elif num==1:\n",
    "                if upper>0 and upper>=lower:\n",
    "                    left.append(1)\n",
    "                    right.append(0)\n",
    "                    upper-=1\n",
    "                elif lower>0:\n",
    "                    left.append(0)\n",
    "                    right.append(1)\n",
    "                    lower-=1\n",
    "                else:\n",
    "                    print([left,right])\n",
    "                    return []\n",
    "            elif num==2:\n",
    "                if upper>0 and lower>0:\n",
    "                    left.append(1)\n",
    "                    right.append(1)\n",
    "                    upper-=1\n",
    "                    lower-=1\n",
    "                else:\n",
    "                    print([left,right])\n",
    "                    return []\n",
    "        return [left,right] if (upper==0 and lower==0) else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        col = len(colsum)\n",
    "        count2 = 0\n",
    "        for i in range(col):\n",
    "            if colsum[i]==2:\n",
    "                count2+=1\n",
    "        ans = [[],[]]\n",
    "        upper -= count2\n",
    "        lower -= count2\n",
    "        if upper<0 or lower<0:return []\n",
    "        for i in range(col):\n",
    "            if colsum[i]==2:\n",
    "                ans[0].append(1)\n",
    "                ans[1].append(1)\n",
    "            elif colsum[i]==1:\n",
    "                if upper>0:\n",
    "                    ans[0].append(1)\n",
    "                    ans[1].append(0)\n",
    "                    upper-=1\n",
    "                elif lower>0:\n",
    "                    ans[0].append(0)\n",
    "                    ans[1].append(1)\n",
    "                    lower-=1\n",
    "                else:\n",
    "                    return []\n",
    "            else:\n",
    "                ans[0].append(0)\n",
    "                ans[1].append(0)\n",
    "        if upper!=0 or lower!=0: return []\n",
    "        return ans\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        if sum(colsum) != lower + upper:\n",
    "            return []\n",
    "        n = len(colsum)\n",
    "        ans = [[0] * n, [0] * n]\n",
    "        index = []\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 2:\n",
    "                ans[0][i] = ans[1][i] = 1\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "                if upper < 0 or lower < 0:\n",
    "                    return []\n",
    "            elif colsum[i] == 1:\n",
    "                index.append(i)\n",
    "        for i in index[:upper]:\n",
    "            ans[0][i] = 1\n",
    "        for i in index[upper:]:\n",
    "            ans[1][i] = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        ret = [[0] * n for _ in range(2)]\n",
    "        seen = [False] * n\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 1:\n",
    "                cnt += 1\n",
    "                continue\n",
    "            seen[i] = True\n",
    "            if colsum[i] == 2:\n",
    "                ret[0][i] = 1\n",
    "                ret[1][i] = 1\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "        if upper < 0 or lower < 0 or cnt != upper + lower:\n",
    "            return []\n",
    "\n",
    "        for i in range(n):\n",
    "            if seen[i]:\n",
    "                continue\n",
    "            if upper > 0:\n",
    "                ret[0][i] = 1\n",
    "                upper -= 1\n",
    "            elif lower > 0:\n",
    "                ret[1][i] = 1\n",
    "                lower -= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "        ret = [[0] * n for _ in range(2)]\n",
    "        seen = [False] * n\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 1:\n",
    "                cnt += 1\n",
    "                continue\n",
    "            seen[i] = True\n",
    "            if colsum[i] == 2:\n",
    "                ret[0][i] = 1\n",
    "                ret[1][i] = 1\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "        if upper < 0 or lower < 0 or cnt != upper + lower:\n",
    "            return []\n",
    "\n",
    "        for i in range(n):\n",
    "            if seen[i]:\n",
    "                continue\n",
    "            if upper > 0:\n",
    "                ret[0][i] = 1\n",
    "                upper -= 1\n",
    "            elif lower > 0:\n",
    "                ret[1][i] = 1\n",
    "                lower -= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        if upper + lower != sum(colsum):\n",
    "            return []\n",
    "        lc = len(colsum)\n",
    "        a1_L = [-1 for i in range(lc)]\n",
    "        a2_L = [-1 for i in range(lc)]\n",
    "        ran_L = []\n",
    "        for i in range(lc):\n",
    "            if colsum[i] == 0:\n",
    "                a1_L[i] = 0\n",
    "                a2_L[i] = 0\n",
    "            elif colsum[i] == 2:\n",
    "                a1_L[i] = 1\n",
    "                a2_L[i] = 1\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "            else:\n",
    "                ran_L.append(i)\n",
    "        if upper < 0 or lower < 0:\n",
    "            return []\n",
    "            \n",
    "        for j in ran_L:\n",
    "            if upper > 0:\n",
    "                a1_L[j] = 1\n",
    "                a2_L[j] = 0\n",
    "                upper -= 1\n",
    "            else:\n",
    "                a1_L[j] = 0\n",
    "                a2_L[j] = 1\n",
    "        return [a1_L, a2_L]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "\n",
    "        upper_list = []\n",
    "        lower_list = []\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            colsum_i = colsum[i]\n",
    "            if colsum_i == 0:\n",
    "                upper_list.append(0)\n",
    "                lower_list.append(0)\n",
    "            elif colsum_i == 1:\n",
    "                if upper >= lower:\n",
    "                    upper_list.append(1)\n",
    "                    lower_list.append(0)\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    upper_list.append(0)\n",
    "                    lower_list.append(1)\n",
    "                    lower -= 1\n",
    "            else:\n",
    "                upper_list.append(1)\n",
    "                lower_list.append(1)\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "            # print(upper_list,lower_list)\n",
    "            if lower < 0 and upper < 0:\n",
    "                return []\n",
    "\n",
    "        if not (lower == 0 and upper == 0):\n",
    "            return []\n",
    "\n",
    "        return [upper_list,lower_list]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        ans1 = []\n",
    "        ans2 = []\n",
    "        for col in colsum:\n",
    "            if upper >= lower:\n",
    "                ans1.append(int(col >= 1))\n",
    "                ans2.append(col - int(col >= 1))\n",
    "                upper -= int(col >= 1)\n",
    "                lower -= (col - int(col >= 1))\n",
    "            else:\n",
    "                ans2.append(int(col >= 1))\n",
    "                ans1.append(col - int(col >= 1))\n",
    "                lower -= int(col >= 1)\n",
    "                upper -= (col - int(col >= 1))\n",
    "\n",
    "        if upper == 0 and lower == 0:\n",
    "            ans.append(ans1)\n",
    "            ans.append(ans2)\n",
    "            return ans\n",
    "        else:\n",
    "            return []\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        ans = [[],[]]\n",
    "        for i in range(len(colsum)):\n",
    "            if colsum[i] == 2:\n",
    "                ans[0].append(1)\n",
    "                ans[1].append(1)\n",
    "                upper = upper - 1\n",
    "                lower = lower - 1\n",
    "            elif colsum[i] == 0:\n",
    "                ans[0].append(0)\n",
    "                ans[1].append(0)\n",
    "            elif colsum[i] == 1:\n",
    "                if upper > lower:\n",
    "                    ans[0].append(1)\n",
    "                    ans[1].append(0)\n",
    "                    upper = upper - 1\n",
    "                else:\n",
    "                    ans[1].append(1)\n",
    "                    ans[0].append(0)\n",
    "                    lower = lower - 1\n",
    "            if upper < 0 or lower < 0:\n",
    "                return []\n",
    "        return ans if upper == lower == 0 else []\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        left,right=[],[]\n",
    "        for num in colsum:\n",
    "            if num==0:\n",
    "                left.append(0)\n",
    "                right.append(0)\n",
    "            elif num==1:\n",
    "                if upper>0 and upper>=lower:\n",
    "                    left.append(1)\n",
    "                    right.append(0)\n",
    "                    upper-=1\n",
    "                elif lower>0:\n",
    "                    left.append(0)\n",
    "                    right.append(1)\n",
    "                    lower-=1\n",
    "                else:\n",
    "                    \n",
    "                    return []\n",
    "            elif num==2:\n",
    "                if upper>0 and lower>0:\n",
    "                    left.append(1)\n",
    "                    right.append(1)\n",
    "                    upper-=1\n",
    "                    lower-=1\n",
    "                else:\n",
    "                   \n",
    "                    return []\n",
    "        return [left,right] if (upper==0 and lower==0) else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        u = []\n",
    "        l = []\n",
    "        for i in colsum:\n",
    "            if i == 0:\n",
    "                u.append(0)\n",
    "                l.append(0)\n",
    "            elif i == 2:\n",
    "                u.append(1)\n",
    "                l.append(1)\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "            elif i == 1:\n",
    "                if upper > lower:\n",
    "                    upper -= 1\n",
    "                    u.append(1)\n",
    "                    l.append(0)\n",
    "                else:\n",
    "                    lower -= 1\n",
    "                    u.append(0)\n",
    "                    l.append(1)\n",
    "            if upper < 0 or lower < 0:\n",
    "                return []\n",
    "        if upper == 0 and upper == 0:\n",
    "            return [u, l]\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: list[int]) -> list[list[int]]:\n",
    "        n = len(colsum)\n",
    "        ans = [[], []]\n",
    "        for i in range(n):\n",
    "            if upper < 0 or lower < 0:\n",
    "                return []\n",
    "            if colsum[i] == 2:\n",
    "                ans[0].append(1)\n",
    "                ans[1].append(1)\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "            elif colsum[i] == 0:\n",
    "                ans[0].append(0)\n",
    "                ans[1].append(0)\n",
    "            else:\n",
    "                if upper > lower:\n",
    "                    ans[0].append(1)\n",
    "                    ans[1].append(0)\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    ans[0].append(0)\n",
    "                    ans[1].append(1)\n",
    "                    lower -= 1\n",
    "        return ans if upper == 0 and lower == 0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        up=[]\n",
    "        low=[]\n",
    "        count2=colsum.count(2)\n",
    "        upper1=upper-count2\n",
    "        for i in range(len(colsum)):\n",
    "            if colsum[i]==0:\n",
    "                up.append(0)\n",
    "                low.append(0)\n",
    "            elif colsum[i]==2:\n",
    "                up.append(1)\n",
    "                low.append(1)\n",
    "            else:\n",
    "                if upper1>0:\n",
    "                    up.append(1)\n",
    "                    low.append(0)\n",
    "                    upper1-=1\n",
    "                else:\n",
    "                    up.append(0)\n",
    "                    low.append(1)\n",
    "        if sum(up)==upper and sum(low)==lower:\n",
    "            return [up, low]\n",
    "        else:\n",
    "            return[]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:       \n",
    "        # Validation\n",
    "        if (upper + lower) != sum(colsum):\n",
    "            return []\n",
    "\n",
    "        ct_2s = colsum.count(2)\n",
    "        if ct_2s > upper:\n",
    "            return []\n",
    "        if ct_2s > lower:\n",
    "            return []\n",
    "\n",
    "        pool = []\n",
    "        upper_ones = upper\n",
    "\n",
    "        ans_upper = []\n",
    "        ans_lower = []\n",
    "        for idx, val in enumerate(colsum):\n",
    "            if val == 1:\n",
    "                pool.append(idx)\n",
    "                ans_upper.append(-1)\n",
    "                ans_lower.append(-1)       \n",
    "            elif val == 2:\n",
    "                ans_upper.append(1)\n",
    "                ans_lower.append(1)                \n",
    "                upper_ones -= 1\n",
    "            else:\n",
    "                ans_upper.append(0)\n",
    "                ans_lower.append(0)\n",
    "        \n",
    "\n",
    "        upper_idxes = next(combinations(pool, upper_ones))\n",
    "\n",
    "        if not upper_idxes:\n",
    "            return []\n",
    "\n",
    "        for idx in pool:\n",
    "            if idx in upper_idxes:\n",
    "                ans_upper[idx] = 1\n",
    "                ans_lower[idx] = 0\n",
    "            else:\n",
    "                ans_upper[idx] = 0\n",
    "                ans_lower[idx] = 1\n",
    "\n",
    "        return [ans_upper, ans_lower]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        n = len(colsum)\n",
    "\n",
    "        upper_list = []\n",
    "        lower_list = []\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            colsum_i = colsum[i]\n",
    "            if colsum_i == 0:\n",
    "                upper_list.append(0)\n",
    "                lower_list.append(0)\n",
    "            elif colsum_i == 1:\n",
    "                if upper >= lower:\n",
    "                    upper_list.append(1)\n",
    "                    lower_list.append(0)\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    upper_list.append(0)\n",
    "                    lower_list.append(1)\n",
    "                    lower -= 1\n",
    "            else:\n",
    "                upper_list.append(1)\n",
    "                lower_list.append(1)\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "            # print(upper_list,lower_list)\n",
    "            # if lower < 0 and upper < 0:\n",
    "            #     return []\n",
    "\n",
    "        if not (lower == 0 and upper == 0):\n",
    "            return []\n",
    "\n",
    "        return [upper_list,lower_list]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        r1 = []\n",
    "        r2 = []\n",
    "        n = len(colsum)\n",
    "        for i in range(n):\n",
    "            if colsum[i] == 0:\n",
    "                r1.append(0)\n",
    "                r2.append(0)\n",
    "            elif colsum[i] == 2:\n",
    "                r1.append(1)\n",
    "                r2.append(1)\n",
    "                upper -= 1\n",
    "                lower -= 1\n",
    "            elif colsum[i] == 1:\n",
    "                if upper >= lower:\n",
    "                    r1.append(1)\n",
    "                    r2.append(0)\n",
    "                    upper -= 1\n",
    "                else:\n",
    "                    r1.append(0)\n",
    "                    r2.append(1)\n",
    "                    lower -= 1\n",
    "        \n",
    "        return [r1, r2] if upper == lower == 0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        matrix=[[],[]]\n",
    "        for col in colsum:\n",
    "            if col==2:\n",
    "                matrix[0].append(1)\n",
    "                matrix[1].append(1)\n",
    "                upper-=1\n",
    "                lower-=1\n",
    "            elif col==0:\n",
    "                matrix[0].append(0)\n",
    "                matrix[1].append(0)\n",
    "            elif upper>lower:\n",
    "                matrix[0].append(1)\n",
    "                matrix[1].append(0)\n",
    "                upper-=1\n",
    "            else:\n",
    "                matrix[1].append(1)\n",
    "                matrix[0].append(0)\n",
    "                lower-=1\n",
    "        return matrix if upper==0 and lower==0 else[]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        #1、创建一个结果\n",
    "        res= [[], []]\n",
    "        #2、先处理和为2的\n",
    "        for i in colsum:\n",
    "            if i==2:\n",
    "                res[0].append(1)\n",
    "                res[1].append(1)\n",
    "                #将一行的和减掉\n",
    "                upper-=1\n",
    "                lower-=1\n",
    "            #3、处理和为0的\n",
    "            elif i==0:\n",
    "                res[0].append(0)\n",
    "                res[1].append(0)\n",
    "            #3、处理和为1的\n",
    "            else:\n",
    "                if upper>=lower:\n",
    "                    res[0].append(1)\n",
    "                    res[1].append(0)\n",
    "                    upper-=1\n",
    "                else:\n",
    "                    res[0].append(0)\n",
    "                    res[1].append(1)\n",
    "                    lower-=1\n",
    "        if upper==0 and lower==0:\n",
    "            return res\n",
    "        else:\n",
    "            return []    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        result = [[], []]\n",
    "\n",
    "        cnt_2 = colsum.count(2)\n",
    "        upper -= cnt_2\n",
    "        lower -= cnt_2\n",
    "        if upper < 0 or lower < 0:\n",
    "            return []\n",
    "\n",
    "        for i in range(len(colsum)):\n",
    "            if colsum[i] == 0 or colsum[i] == 2:\n",
    "                val = colsum[i] // 2\n",
    "                result[0].append(val)\n",
    "                result[1].append(val)\n",
    "            else:\n",
    "                if upper > 0:\n",
    "                    result[0].append(1)\n",
    "                    result[1].append(0)\n",
    "                    upper -= 1\n",
    "                elif lower > 0:\n",
    "                    result[0].append(0)\n",
    "                    result[1].append(1)\n",
    "                    lower -= 1\n",
    "                else:\n",
    "                    return []\n",
    "        return result if upper == 0 and lower == 0 else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        l = len(colsum)\n",
    "        if upper>l or lower>l:\n",
    "            return []\n",
    "        ans = [[],[]]\n",
    "        for i in range(l):\n",
    "            ans[0].append(0)\n",
    "            ans[1].append(0)\n",
    "            if colsum[i]==2:\n",
    "                ans[0][i]=1\n",
    "                ans[1][i]=1\n",
    "                upper-=1\n",
    "                lower-=1\n",
    "        if upper<0 or lower<0:\n",
    "            return []\n",
    "        for i in range(l):\n",
    "            if colsum[i]==1 and upper>0:\n",
    "                ans[0][i] = 1\n",
    "                upper-=1\n",
    "            elif colsum[i]==1:\n",
    "                ans[1][i] = 1\n",
    "                lower-=1\n",
    "        if lower!=0 or upper!=0:\n",
    "            return []\n",
    "        else:\n",
    "            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        dp = [[0]*len(colsum) for i in range(2)]\n",
    "        res = []\n",
    "        for i in range(len(colsum)):\n",
    "            if colsum[i]==2:\n",
    "                if upper>0 and lower>0:\n",
    "                    upper-=1\n",
    "                    lower-=1\n",
    "                    dp[0][i]+=1\n",
    "                    dp[1][i]+=1\n",
    "                else:\n",
    "                    return []\n",
    "            elif colsum[i]==1:\n",
    "                res.append(i)\n",
    "        if upper+lower!=len(res):\n",
    "            return []\n",
    "        for i in res:\n",
    "            if upper:\n",
    "                dp[0][i]+=1\n",
    "                upper-=1\n",
    "            else:\n",
    "                dp[1][i]+=1\n",
    "                lower-=1\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        res=[[],[]]\n",
    "        for c in colsum:\n",
    "            if c==0:\n",
    "                res[0].append(0)\n",
    "                res[1].append(0)\n",
    "            elif c==2:\n",
    "                res[0].append(1)\n",
    "                res[1].append(1)\n",
    "                upper-=1\n",
    "                lower-=1\n",
    "            else:\n",
    "                if upper>lower:\n",
    "                    res[0].append(1)\n",
    "                    res[1].append(0)\n",
    "                    upper-=1\n",
    "                else:\n",
    "                    res[0].append(0)\n",
    "                    res[1].append(1)\n",
    "                    lower-=1\n",
    "        return res if upper==lower==0 else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        result_list = [[0 for j in range(len(colsum))] for i in range(2)]\n",
    "        for i in range(len(colsum)):\n",
    "            if colsum[i] == 2:\n",
    "                result_list[0][i] = 1\n",
    "                upper -= 1\n",
    "        for i in range(len(colsum)):\n",
    "            if upper == 0:\n",
    "                break\n",
    "            if colsum[i] == 1:\n",
    "                result_list[0][i] = 1\n",
    "                upper -= 1\n",
    "        print(result_list)\n",
    "        for i in range(len(colsum)):\n",
    "            if colsum[i] == 2:\n",
    "                result_list[1][i] = 1\n",
    "                lower -= 1\n",
    "        \n",
    "        for i in range(len(colsum)):\n",
    "            if colsum[i] == 1 and result_list[0][i] != 1:\n",
    "                result_list[1][i] = 1\n",
    "                lower -= 1\n",
    "        print(result_list)\n",
    "        if lower != 0 or upper != 0:\n",
    "            return []\n",
    "        return result_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:\n",
    "        res=[[0]*len(colsum) for _ in range(2)]\n",
    "        lis=[]\n",
    "        for i in range(len(colsum)):\n",
    "            if colsum[i]==2:\n",
    "                res[0][i],res[1][i]=1,1\n",
    "                upper-=1\n",
    "                lower-=1\n",
    "            elif colsum[i]==0:\n",
    "                res[0][i],res[1][i]=0,0\n",
    "            else:\n",
    "                lis.append(i)\n",
    "        for j in lis:\n",
    "            if upper!=0:\n",
    "                res[0][j]=1\n",
    "                upper-=1\n",
    "            else:\n",
    "                res[1][j]=1\n",
    "                lower-=1\n",
    "        return res if upper==0 and lower==0 else []"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
